\chapter{Вопрос №7}

Задачи о подсчете количества раскладок $n$ различимых предметов по $k$ неразличимым ящикам. Числа Стирлинга второго рода, рекуррентное соотношение для них. Числа Белла, их комбинаторный смысл, рекуррентное соотношение для чисел Белла.

\section{Раскладки и числа Стирлинга}

Известно, что число упорядоченных разбиений $n$-множества $X$ на $k$ блоков равно числу Моргана $$ \hat S\left(n,k\right) $$. Рассмотрим теперь неупорядоченные разбиения (или просто $k$-разбиения) множества $X$ на $k$ блоков, обозначим число таких разбиений через $S\left(n,k\right)$.

Очевидно, между $\hat S\left(n,k\right)$ и $S\left(n,k\right)$ имеется следующая связь:
\begin{equation}
	\hat S\left(n,k\right) = k! S\left(n,k\right)
\end{equation}
так как упорядочить $k$ блоков разбиения можно $k!$ способами, следовательно справедливы формулы:
\begin{equation}
	S\left(n,k\right) = \frac{1}{k!} \sum_{i=0}^k \left(-1\right)^{i}\binom{k}{i}\left(k-i\right)^n = \frac{1}{k!}\sum_{{{a_1 + ... a_k = n}\atop{a_i > 0}}} P\left(n; a_1, ..., a_k\right)
\end{equation}

Числа $S\left(n,k\right)$ определят количество неупорядоченныз разбиений $n$-множества на $k$ блоков, и называются числами Стирлинга второго рода. Обычно для них используется обозначение: $$ \Stirsecond{n}{k} $$

\section{Рекуррентная формула}

\begin{equation}
\Stirsecond{n}{k} = \Stirsecond{n-1}{k-1} + k\Stirsecond{n-1}{k}
\end{equation}
при начальных условиях:
\[
	\Stirsecond{n}{1} = 1; \Stirsecond{n}{k} = 0, \forall k > n
\]
\begin{Proof}
Разобьем все разбиения на два непересекающихся класса:
\begin{enumerate}
\item К первому классу относятся разбиения, в которых присутствует блок состоящий из одного элемента $n$. Число таких разбиений очевидно равно: $$ \Stirsecond{n-1}{k-1} $$

\item Ко второму классу относятся разбиения, в которых элементв $n$ входит в блок размера 2 или более. Каждому из таких разбиений можно сопоставить разбиение из $n-1$ элемента на $k$ блоков, добавив в один из блоков элемент $n$, а следовательно количество таких разбиений равно $$ k\Stirsecond{n-1}{k}$$
\end{enumerate}
\end{Proof}

\section{Числа Белла}

Пусть теперь нам не важно на какое количество блоков мы разбиваем $X$ множество, т. е. мы рассматриваем все разбиения $n$-множества $X$, очевидно, что разбить $n$-множество на более чем $n$ блоков нельзя, следовательно имеем:
\begin{equation}
	B_n = \sum_{k=0}^n \Stirsecond{n}{k}
\end{equation}
Эти числа называются числами Белла.

Для чисел $B_n$ справедлива рекуррентная формула:
\begin{equation}
	B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k
\end{equation}
при начальных условиях:
\[
	B_0 = 1
\]
\begin{Proof}
Разобьем все разбиения $n+1$ множества на классы следующим образом: в $i$-ый блок $X_i$ попадают только такие разбиения, в которых элемент $n+1$ содержится в блоке мощности $i+1$. Очевидно, что сформировать $X_i$ можно $$ \binom{n}{i} $$
оставшиеся $n-i$ элементов можно разбить на блоки $B_{n-i}$ способами, суммируя по всем $i \in \left\{0,...,n\right\}$ получаем $$ B_{n+1} = \sum_{i=0}^n \binom{n}{i} B_{n-i}  = \sum_{i=0}^n\binom{n}{n-i}B_{n-i}$$
\end{Proof}
